/* lr0.c - Code to implement LR(0) parser construction.
 */

#include "globals.h"
#include "lr0.h"
#include "symtab.h"

static void         ComputeLR0(TSymbol* NonTerm);
static TItemSet*    CreateInitialItems(TSymbol* RootSymbol);
static int          StateFromItemSet(TStates* States, TItemSet* Items);
static TItemSet*    ItemsNew(TItemSet* Copy);
static void         ItemsDelete(TItemSet* Items);
static void         ItemsAdd(TItemSet* Items, TITEM Item);
static void         ItemsExpand(TItemSet* Items, TSymbol* Symbol);
static TITEM        AdvanceItem(TSymbol* NonTerm, TStates* States, int iState, int iItem);
static TSymbol*     GetItemSymbol(TSymbol* NonTerm, TStates* States, int iState, int iItem);
static void         AddTransition(TStates* States, int State, int ToState, TSymbol* Symbol);
static void         ItemsAddAll(TItemSet* Items, TSymbol* NonTerm);
static void         DumpLR0(TSymbol* Symbol);
static void         CheckLR0(TSymbol* Symbol);
static void         PostProcess(TSymbol* RootSymbol, TStates* States);

/* ComputeAllLR0() - compute zero or more LR(0) state machines.
 */
void    ComputeAllLR0(void)
    {
    SymIt   NonTerm = SymItNew(Globals.NonTerms);

    while(SymbolIterate(&NonTerm))
        if(NonTerm.Symbol->OperatorTrigger)
            {
            ComputeLR0(NonTerm.Symbol);
            if(Globals.Dump)
                DumpLR0(NonTerm.Symbol);
            CheckLR0(NonTerm.Symbol);
            }
    }


/* EquivTokens() - return true if two symbols are "equivalent".
 *
 * Equivalent here just means they produce identical transitions in
 * every single state.
 */
static
int     EquivTokens(TStates* States, TSymbol* Sym1, TSymbol* Sym2)
    {
    int     Result  = TRUE;
    int     iState;

    for(iState=0; Result && iState < States->Count; ++iState)
        {
        TState*         State       = States->States[iState];
        int             NextState   = -1;
        int             iTransition;
        TTransitions*   Transitions;
        
        Transitions = &State->Transitions;
        for(iTransition=0; iTransition < Transitions->Count; ++iTransition)
            {
            TTransition Transition = State->Transitions.Transitions[iTransition];

            /* if transition is on either of our symbols */
            if(Transition.Symbol == Sym1 || Transition.Symbol == Sym2)
                {
                /* if first match of a symbol, record its next state */
                if(NextState == -1)
                    NextState   = Transition.NextState;
                /* else see if the two symbols transit to the same state */
                else if(NextState == Transition.NextState)
                    {
                    NextState   = -1;
                    break;
                    }
                /* else, two symbols don't match */
                else
                    break;
                }
            }
        if(NextState != -1)
            {
            Result  = FALSE;
            break;
            }
        }
    return Result;
    }

/* ComputeTokenClasses() - create groups of tokens the DFA sees as equivalent.
 *
 * create stack of unique operator tokens used by DFA
 * while stack not empty
 *     create new token class
 *     pop optoken off stack
 *     for each optoken on stack
 *        if equiv to this optoken
 *            add it to this token class
 *            remove it from stack
 */
static
void    ComputeTokenClasses(TStates* States)
    {
    int     TokenClassSize, iTokenClass;
    SYMBOLS Stack;

    SymbolListDump(stdout, States->OpTokens, ",and");
    fprintf(stdout, "\n^^^^^^^^^^^^^ %d unique operator tokens \n", SymbolListCount(States->OpTokens));
    /* create our token class array */
    TokenClassSize  = SymbolListCount(States->OpTokens);    /* worst case size */
    assert(TokenClassSize > 0);
    States->TokenClasses    = calloc(TokenClassSize, sizeof(SYMBOLS));
    assert(States->TokenClasses != NULL);

    Stack   = SymbolListCopy(NULL, States->OpTokens);
    for(iTokenClass=0; SymbolListCount(Stack); ++iTokenClass)
        {
        TSymbol*    ThisOpToken;
        TSymbol*    OtherOpToken;
        SYMBOLS     NewClass = SymbolListCreate();
        int         iOpToken;

        ThisOpToken = SymbolListPop(Stack);
        NewClass    = SymbolListAdd(NewClass, ThisOpToken);
        for(iOpToken=0; iOpToken < SymbolListCount(Stack); ++iOpToken)
            {
            OtherOpToken    = SymbolListGet(Stack, iOpToken);

            if(EquivTokens(States, ThisOpToken, OtherOpToken))
                {
                NewClass    = SymbolListAdd(NewClass, OtherOpToken);
                SymbolListDelete(Stack, iOpToken);
                --iOpToken;
                }
            }
        assert(iTokenClass < TokenClassSize);
        States->TokenClasses[iTokenClass] = NewClass;

        fprintf(stdout, "TokenClass[%d] = ", iTokenClass);
        SymbolListDump(stdout, NewClass, ",and");
        fprintf(stdout, "\n");

        }
    
    }

static
void         CheckLR0(TSymbol* Symbol)
    {
    int         iState, iRule, Dot, iItem, iProdItem, NProdItems, ReduceCount;
    TStates*    States  = Symbol->LR0;
    TRule*      Rule;

    if(Globals.Dump && Globals.Verbose)
        Dump("CheckLR0('%s')\n", SymbolStr(Symbol));

    for(iState=0; iState < States->Count; ++iState)
        {
        TState*     State   = States->States[iState];
        TItemSet*   Items   = &State->ItemSet;
        int*        ReduceRules;
        
        ReduceRules = calloc(Items->Count, sizeof(int));
        assert(ReduceRules != NULL);

        /* check for reduce-reduce conflicts */
        for(ReduceCount=iItem=0; iItem < Items->Count; ++iItem)
            {
            iRule       = Items->Items[iItem] >> 16;
            Dot         = Items->Items[iItem] & 0x7FFF;
            Rule        = Symbol->Rules[iRule];
            NProdItems  = SymbolListCount(Rule->Symbols);
            if(Dot == NProdItems)
                {
                ++ReduceCount;
                ReduceRules[iItem]  = 1;
                }
            }
        if(ReduceCount > 1)
            {
            ErrorPrologue(ERROR_REDUCE_REDUCE_CONFLICT);
            Error("reduce/reduce conflict in '%s' between:\n", SymbolStr(Symbol));
            for(iItem=0; iItem < Items->Count; ++iItem)
                if(ReduceRules[iItem])
                    {
                    iRule       = Items->Items[iItem] >> 16;
                    Dot         = Items->Items[iItem] & 0x7FFF;
                    Rule        = Symbol->Rules[iRule];
                    NProdItems  = SymbolListCount(Rule->Symbols);
                    Error("    -> ");
                    for(iProdItem=0; iProdItem < NProdItems; ++iProdItem)
                        Error("%s ", SymbolStr(SymbolListGet(Rule->Symbols, iProdItem)));
                    Error("\n");
                    }
            ErrorEpilog(0);
            }
        /* check for shift-reduce that we can't handle */
        free(ReduceRules);
        }
    }

/* ComputeLR0() - Compute the LR(0) state machine for this nonterminal
 */
static
void ComputeLR0(TSymbol* NonTerm)
    {
    TItemSet*   Items;
    int         State       = 0;
    TStates*    States      = NEW(TStates);
    TState*     ThisState;

    assert(States != NULL);
    
    if(Globals.Verbose)
        fprintf(stdout, "Compute LR(0) machine for '%s'\n", SymbolStr(NonTerm));
    /* create state 0 */
    Items       = CreateInitialItems(NonTerm);
    StateFromItemSet(States, Items);
    ItemsDelete(Items);

    /* now process each state (which possibly creates new, unprocessed states) */
    for(State = 0; State < States->Count; ++State)
        {
        SYMBOLS     Processed   = NULL;
        TSymbol*    Symbol;
        int         iItem, jItem, NItems, ToState;
        
printf("------>state %d/%d\n", State, States->Count);
        ThisState   = States->States[State];    /* grab next unprocessed state */
        NItems      = ThisState->ItemSet.Count;

        /* find an unprocessed symbol that follows the dot */
        for(iItem = 0; iItem < NItems; ++iItem)
            if((Symbol=GetItemSymbol(NonTerm, States, State, iItem))!= NULL
            && !SymbolListContains(Processed, Symbol)
              )
                {
printf("    ------>iItem %d, Symbol=%s\n", iItem, SymbolStr(Symbol));
                /* create an empty item list */
                Items       = ItemsNew(NULL);
                for(jItem = iItem; jItem < NItems; ++jItem)
                    if(GetItemSymbol(NonTerm, States, State, jItem) == Symbol)
                        ItemsAdd(Items, AdvanceItem(NonTerm, States, State, jItem));
                ItemsExpand(Items, NonTerm);
                ToState    = StateFromItemSet(States, Items);
                ItemsDelete(Items);
                AddTransition(States, State, ToState, Symbol);
                /* remember that we processed this symbol */
                Processed   = SymbolListAdd(Processed, Symbol);
                }
else printf("    ------>iItem %d, [Symbol=%p %s]\n", iItem, Symbol, Symbol?SymbolStr(Symbol):"");
        SymbolListDestroy(Processed);
        }
    PostProcess(NonTerm, States);
    ComputeTokenClasses(States);
    NonTerm->LR0    = States;
printf("Compute LR(0) is done\n");
    }

/* PostProcess() - make another pass over the final list of states.
 *
 * This is a good time to mark which states are accepting, and to
 * add a transition on BLC_EOF to one special state.
 */
static
void PostProcess(TSymbol* RootSymbol, TStates* States)
    {
    TItemSet*   Items;
    int         iState, jState;
    int         FinalCount;
    TState*     State;

    /* for each state */
    FinalCount  = 0;
    for(iState = 0; iState < States->Count; ++iState)
        {
        int         iItem, NItems;
        int         Final;
        
        State   = States->States[iState];
        NItems      = State->ItemSet.Count;
        Items       = &State->ItemSet;

        /* for each item in this state */
        Final   = TRUE;
        for(iItem = 0; iItem < NItems; ++iItem)
            {
            int     iRule, Dot,NProdItems;
            TRule*  Rule;
            
            iRule       = Items->Items[iItem] >> 16;
            Dot         = Items->Items[iItem] & 0x7FFF;
            Rule        = RootSymbol->Rules[iRule];
            NProdItems  = SymbolListCount(Rule->Symbols);
            if(Dot >= NProdItems)
                State->Accepting    = TRUE;
            /* every item in the "final" state must look like this:
             *     expr -> expr . [...]
             * If we had faked an initial S -> expr $, then the final
             * state would have been the one doing that reduction.
             */
            if(Dot != 1 || SymbolListGet(Rule->Symbols, 0) != RootSymbol)
                Final   = FALSE;
            }
        if(Final)
            {
            ++FinalCount;
            State->Final    = Final;
            AddTransition(States, iState, 0, SymbolFind(EOFToken));
            }
        /* see if all inbound transitions are identical */
        State->Inbound  = -1;   /* -1 means no inbound transitions */
        for(jState=0; jState < States->Count; ++jState)
            {
            TState*         Other   = States->States[jState];
            int             NTrans  = Other->Transitions.Count;
            TTransition*    Trans   = Other->Transitions.Transitions;
            int             iTrans;
        
            for(iTrans=0; iTrans < NTrans; ++iTrans)
                {
                }

            for(iItem=0; iItem < Items->Count; ++iItem)
                {
                int     iRule, Dot,NProdItems;
                TRule*  Rule;
            
                }
            }

        }
//    assert(FinalCount == 1);

    }


/*  CreateInitialItems() - create initial item set.
 *
 *  We create an item set containing one item for each
 *  rule in the root symbol. For example, if the root
 *  symbol looks like this:
 *      E -> '-' E
 *         | E '-' E
 *         | TK_ID
 *  then our item set would be:
 *      E -> .'-' E
 *      E -> .E '-' E
 *      E -> .TK_ID
 *
 *  Note that the initial state cannot be an accepting state
 *  because E is not allowed to be nullable.
 */
static
TItemSet*    CreateInitialItems(TSymbol* RootSymbol)
    {
    int         iRule;
    TItemSet*   Result = NEW(TItemSet);

    assert(Result != NULL);

    Result->Count   = RootSymbol->NRules;
    assert(Result->Count >= 0);

    Result->Items   = calloc(Result->Count, sizeof(TITEM));
    assert(Result->Items != NULL);

    for(iRule = 0; iRule < Result->Count; ++iRule)
        Result->Items[iRule]    = (iRule << 16) | 0;

    return Result;
    }


/*  ItemsNew() - Create a new itemset (possibly a copy of an existing one)
 *
 */
static
TItemSet*    ItemsNew(TItemSet* Copy)
    {
    TItemSet*   Result;

    Result      = NEW(TItemSet);
    if(Copy)
        {
        Result->Count   = Copy->Count;
        if(Result->Count)
            {
            Result->Items   = calloc(Copy->Count, sizeof(TITEM));
            memcpy(Result->Items, Copy->Items, Copy->Count * sizeof(TITEM));
            }
        }
    return Result;
    }

static
void    ItemsDelete(TItemSet* Items)
    {
    if(Items->Items)
        free(Items->Items);
    free(Items);
    }


/*  ItemsExpand() - perform closure on this item set.
 *
 *  Suppose there is an item whose dot is followed by a non-terminal:
 *      E -> '(' E ')' .E
 *  In that case, for every production of the form E -> X, we must add
 *  an item of E -> .X
 */
static
void    ItemsExpand(TItemSet* Items, TSymbol* NonTerm)
    {
    int         iItem, iRule, iDot, NProdItems;
    TRule*      Rule;
    TSymbol*    Symbol;

    for(iItem = 0; iItem < Items->Count; ++iItem)
        {
        iRule       = Items->Items[iItem] >> 16;
        assert(iRule >= 0 && iRule < NonTerm->NRules);
        Rule        = NonTerm->Rules[iRule];
        NProdItems  = SymbolListCount(Rule->Symbols);
        iDot        = Items->Items[iItem] & 0x7FFF;
        assert(iDot >= 0 && iDot <= NProdItems);
        /* if dot is not after final symbol on rhs */
        if(iDot < NProdItems)
            {
            Symbol  = SymbolListGet(Rule->Symbols, iDot);
            if(Symbol == NonTerm)
                {
                ItemsAddAll(Items, NonTerm);
                break;
                }
            }
        }
    }

/* ItemsAddAll() - add all rules of nonterminal as items.
 *
 *  For example, if E -> '-' E | E '-' E | '(' E ')'
 *  then we would create items:
 *      E -> . '-' E
 *      E -> . E '-' E
 *      E -> . '(' E ')'
 */
static
void    ItemsAddAll(TItemSet* Items, TSymbol* NonTerm)
    {
    int     iRule;

    for(iRule = 0; iRule < NonTerm->NRules; ++iRule)
        ItemsAdd(Items, iRule << 16);
    }

static
void    ItemsDump(TItemSet* Items)
    {
    int     iItem;

    fprintf(stdout, "Dump TItemSet, Count=%d\n", Items->Count);
    for(iItem = 0; iItem < Items->Count; ++iItem)
        {
        fprintf(stdout, "    [%2d] 0x%08X\n", iItem, Items->Items[iItem]);
        }
    }

/*  ItemsAdd() - add an item to an item set.
 * 
 *  Since this is a set, the new item is not added if it is
 *  already present.
 */
static
void         ItemsAdd(TItemSet* Items, TITEM Item)
    {
    int     iItem;

    if(Item != -1)  /* -1 means no item to add */
        {
        DumpVerbose("ItemsAdd(0x%08X) rule=%d, dot=%d\n", Item, Item >> 16, Item & 0x7FFF);
        for(iItem = 0; iItem < Items->Count; ++iItem)
            if(Items->Items[iItem] == Item)
                break;
        if(iItem >= Items->Count)
            {
            Items->Items    = realloc(Items->Items, (++Items->Count)*sizeof(TITEM));
            Items->Items[iItem] = Item;
            }
        }
    if(Globals.Dump && Globals.Verbose)
        ItemsDump(Items);
    }

static
TITEM   ItemFromItemPos(TStates* States, int iState, int iItem)
    {
    TItemSet*   Items;
    TITEM       Item;
    
    assert(iState >= 0);
    assert(iState < States->Count);
    assert(States->States[iState] != NULL);
    Items   = &States->States[iState]->ItemSet;
    assert(iItem >= 0);
    assert(iItem < Items->Count);
    Item    = Items->Items[iItem];

    DumpVerbose("ItemFromItemPos(state=%d, iItem=%d)=0x%08X\n", iState, iItem, Item);
    return Item;
    }

/* GetItemSymbol() - return symbol following dot in an item.
 *
 *  Suppose a state contains these items:
 *      E -> '(' E ')'.
 *      E -> '(' E ')' .E
 *      E -> .'-' E
 *  For this state, GetItemSymbol(..., 0) would return NULL,
 *  GetItemSymbol(..., 1) would return the TSymbol* for 'E',
 *  and GetItemSymbol(...,2) would return the TSymbol* for '-'.
 */
static
TSymbol*    GetItemSymbol(TSymbol* NonTerm, TStates* States, int iState, int iItem)
    {
    TItemSet*   Items;
    TITEM       Item;
    int         iRule, iPos;
    TRule*      Rule;
    TSymbol*    Result;
    
    assert(iState >= 0);
    assert(iState < States->Count);
    assert(States->States[iState] != NULL);
    Items   = &States->States[iState]->ItemSet;
    assert(iItem >= 0);
    assert(iItem < Items->Count);
    Item    = Items->Items[iItem];
    iRule   = Item >> 16;
    iPos    = Item & 0x7FFF;
    Rule    = NonTerm->Rules[iRule];

    /* returns NULL if iPos past end */
    Result  = SymbolListGet(Rule->Symbols, iPos);

    return Result;
    }

/*  StateFromItemSet() - return # of state associated with an item set.
 *
 *  Given an item set, this function locates an existing state that
 *  has that identical item set. If no such state exists, it is created
 *  and added to the end. The return value is the (zero-based) integer
 *  offset of the state.
 */
static int ItemCmp(const void* A, const void* B)
    {  return *(const int*)A - *(const int*)B; }
static
int     StateFromItemSet(TStates* States, TItemSet* Items)
    {
    TState* NewState;
    int     iItem, iState;

    if(Items->Count <= 0)
        return -1;
    /* sort item lists for ease of comparing */
    qsort(Items->Items, (size_t)Items->Count, sizeof(TITEM), ItemCmp);
    for(iState = 0; iState < States->Count; ++iState)
        if(States->States[iState]->ItemSet.Count == Items->Count)
            {
            for(iItem = 0; iItem < Items->Count; ++iItem)
                if(States->States[iState]->ItemSet.Items[iItem] != Items->Items[iItem])
                    break;
            /* if an existing state matches */
            if(iItem >= Items->Count)
                return iState;
            }
    /* have to create a new state */
    States->States = realloc(States->States, (States->Count+1)*sizeof(TState*));
    assert(States->States != NULL);
    
    NewState    = NEW(TState);
    assert(NewState != NULL);

    NewState->ItemSet.Count = Items->Count;
    NewState->ItemSet.Items = calloc(Items->Count, sizeof(TITEM));
    assert(NewState->ItemSet.Items != NULL);
    memcpy(NewState->ItemSet.Items, Items->Items, Items->Count*sizeof(TITEM));
    States->States[States->Count]   = NewState;
    if(Globals.Dump)
        {
        int     iItem;
        
        fprintf(stdout, "Create new state %d\n", States->Count);
        for(iItem = 0; iItem < NewState->ItemSet.Count; ++iItem)
            {
            TITEM   Item    = NewState->ItemSet.Items[iItem];
            int     iRule   = Item >> 16;
            int     Dot     = Item & 0x7FFF;

            fprintf(stdout, "    (0x%08X) rule %d, dot=%d\n", Item, iRule, Dot);
            }
        }

    return States->Count++;
    }

/*  AdvanceItem() - Advance the item's dot!
 *
 *  Suppose we have an item like this:
 *      E -> '(' .E ')'
 *  Then AdvanceItem() would return this item:
 *      E -> '(' E .')'
 *
 *  An attempt to advance past the last position returns -1.
 */
static
TITEM   AdvanceItem(TSymbol* NonTerm, TStates* States, int iState, int iItem)
    {
    TITEM   Item;
    int     iRule, DotPos;
    TRule*  Rule;

    Item    = ItemFromItemPos(States, iState, iItem);
    iRule   = Item >> 16;
    DotPos  = Item & 0x7FFF;

    assert(iRule >= 0);
    assert(iRule < NonTerm->NRules);
    Rule    = NonTerm->Rules[iRule];
    assert(DotPos >= 0);
    assert(DotPos <= SymbolListCount(Rule->Symbols));
    if(DotPos >= SymbolListCount(Rule->Symbols))
        Item    = -1;
    else
        Item    = (iRule << 16) | ++DotPos;

    if(Globals.Dump)
        fprintf(stdout, "AdvanceItem(state=%d, item=%d) [rule %d, dot %d] returns 0x%08X\n",
                iState, iItem, iRule, DotPos-1, Item);
    return Item;
    }

/*  AddTransition() - add a transition to a state.
 *
 *  A transition consists of a symbol and a destination state.
 *  It is benign to attempt to add a transition that already
 *  exists in the given state. If Symbol is actually a non-terminal
 *  representing a list of operators, then we "explode" that list
 *  here, and act on the entire list.
 *
 * As a side-effect, this function also (may) add Symbol to the States
 * OpTokens array of unique operator tokens seen.
 */
static
void    AddTransition(TStates* States, int iState, int ToState, TSymbol* Symbol)
    {
    int             iTransition;
    TState*         State;
    TTransition     Transition  = {0};
    TTransitions*   Transitions;
    SYMBOLS         List        = SymbolListAdd(NULL, Symbol);
    SymIt           ThisSym;

    if(ToState == -1)
        return;
    if(Globals.Dump)
        fprintf(stdout, "AddTransition from %d -> %d on symbol '%s'\n",
                iState, ToState, SymbolStr(Symbol));
    /* "explode" Symbol if necessary */
//    if(SymbolIsOpSyms(Symbol))
// ??? TODO just copy list
    if(Symbol->OpAbbrev)
        List    = SymbolGetAllSymbols(Symbol);
    else
        List    = SymbolListAdd(NULL, Symbol);

    ThisSym     = SymItNew(List);
    while(SymbolIterate(&ThisSym))
        {
        Symbol      = ThisSym.Symbol;

        States->OpTokens    = SymbolListAddUnique(States->OpTokens, Symbol);
        State       = States->States[iState];
        Transitions = &State->Transitions;
        for(iTransition=0; iTransition < Transitions->Count; ++iTransition)
            {
            Transition = Transitions->Transitions[iTransition];

            if(Transition.Symbol == Symbol && Transition.NextState == ToState)
                break;
            }
        /* if transition does not already exist */
        if(iTransition >= Transitions->Count)
            {
            Transition.NextState    = ToState;
            Transition.Symbol       = Symbol;
            Transitions->Transitions = realloc(Transitions->Transitions, (State->Transitions.Count+1)*sizeof(TTransition));
            Transitions->Transitions[Transitions->Count++]  = Transition;
            }
        }
    }


/* DumpLR0() - dump the LR(0) machine associated with a given symbol.
 */
static
void         DumpLR0(TSymbol* Symbol)
    {
    int         iState;
    TStates*    States = Symbol->LR0;

    assert(States != NULL);
    
    fprintf(stdout, "LR(0) machine for '%s', %d States\n", SymbolStr(Symbol), States->Count);
    for(iState=0; iState < States->Count; ++iState)
        {
        TState*     State   = States->States[iState];
        TItemSet*   Items   = &State->ItemSet;
        int         iItem, iTrans;
        int         HasShift = FALSE;
        
        /* first, calculate whether this is an accepting state or not */
        State->Accepting   = FALSE;
        for(iItem=0; iItem < Items->Count; ++iItem)
            {
            int     iRule, Dot,NProdItems;
            TRule*  Rule;
            
            iRule   = Items->Items[iItem] >> 16;
            Dot     = Items->Items[iItem] & 0x7FFF;
            Rule    = Symbol->Rules[iRule];
            NProdItems  = SymbolListCount(Rule->Symbols);
            if(Dot >= NProdItems)
                State->Accepting    = TRUE;
            else
                HasShift            = TRUE;
            if(State->Accepting && HasShift)
                break;
            }

        fprintf(stdout, "State %d, %d items  %s %s\n",
                iState, Items->Count,
            State->Accepting?(HasShift?"AMBIGUOUS":"ACCEPTING"):"",
                State->Final?"FINAL":"");

        for(iItem=0; iItem < Items->Count; ++iItem)
            {
            int     iRule, Dot, iProdItem, NProdItems;
            TRule*  Rule;
            
            iRule   = Items->Items[iItem] >> 16;
            Dot     = Items->Items[iItem] & 0x7FFF;
            Rule    = Symbol->Rules[iRule];
            NProdItems  = SymbolListCount(Rule->Symbols);
            fprintf(stdout, "%s   %s -> ",
                    (Dot >= NProdItems) ? "A" : " ",
                    SymbolStr(Symbol));
            for(iProdItem=0; iProdItem < NProdItems; ++iProdItem)
                fprintf(stdout, "%s%s ", 
                    (iProdItem == Dot)?".":"",
                    SymbolStr(SymbolListGet(Rule->Symbols, iProdItem)));
            fprintf(stdout, "%s\n", (Dot == NProdItems) ? "." : "");
            }
        for(iTrans=0; iTrans < State->Transitions.Count; ++iTrans)
            {
            fprintf(stdout, "    [%s]->%d\n",
                    SymbolStr(State->Transitions.Transitions[iTrans].Symbol),
                    State->Transitions.Transitions[iTrans].NextState);
            }
        }
    }

